The present invention relates to computer networks and, more particularly, to traffic management and flow prioritization across communication circuits (especially virtual circuits).
Data communication in a computer network involves the exchange of data between two or more entities interconnected by communication links and subnetworks. These entities are typically software programs executing on hardware computer platforms, which, depending on their roles within the network, may serve as end stations or intermediate stations. Examples of intermediate stations include routers, bridges and switches that interconnect communication links and subnetworks; an end station may be a computer located on one of the subnetworks. More generally, an end station connotes a source of or target for data that typically does not provide routing or other services to other computers on the network. A local area network (LAN) is an example of a subnetwork that provides relatively short-distance communication among the interconnected stations; in contrast, a wide area network (WAN) facilitates long-distance communication over links provided by public or private telecommunications facilities.
End stations typically communicate by exchanging discrete packets or frames of data according to predefined protocols. In this context, a protocol represents a set of rules defining how the stations interact with each other to transfer data. Such interaction is simple within a LAN, since these are typically xe2x80x9cbroadcastxe2x80x9d networks: when a source station transmits a frame over the LAN, it reaches all stations on that LAN. If the intended recipient of the frame is connected to another network, the frame is passed over a routing device to that other network. Collectively, these hardware and software components comprise a communications network and their interconnections are defined by an underlying architecture.
Traffic flowing through a network may be considered as a set of flows. A flow consists of a set of packets that require similar treatment by the network. Flows may be defined according to a wide range of criteria to meet different needs. For example, a flow could be the set of packets sent from one host to another, or it could be the set of packets exchanged by a pair of communicating application programs. In general there may be many flows passing through any point in the network at any time.
Packets travel between network entities over xe2x80x9ccircuitsxe2x80x9d connecting the entities. The traditional circuit is a physical transmission line between the communicating stations, and over which data is exchanged. The circuit is defined by a communication subnetwork that carries messages between connected entities the way the telephone system connects callersxe2x80x94i.e., over wires or optical fibers intercommunicating through switches. Accordingly, the physical circuit is continuously dedicated to the transmission path between connected entities; data exchange is synchronous over the path in the sense of being tied to a common master clock.
This mode of communication absorbs substantial bandwidth. Unless data moves constantly between the communicating entities, the circuit will at times be idle and the bandwidth consequently wasted. To avoid this, networks frequently employ xe2x80x9cvirtualxe2x80x9d circuits rather than dedicated transmission lines. The virtual circuit establishes a routing pathway for message travel between communicating stations, and is virtual in the sense that many stations can transmit across the lines defining the circuit; these are not dedicated to a single pair of entities. Different types of networks employ the virtual circuit (VC) model of communication, most notably Frame Relay and Asynchronous Transfer Mode (ATM).
ATM can accommodate constant-rate and variable-rate data traffic. The VC may be established by a SETUP message, which travels through a sequence of switches until it reaches the destination station, thereby establishing the VC path. In general, a VC may carry many flows at one time.
A representative ATM configuration is shown in FIG. 1. A single VC interconnects router 25 and router 27. An end station 10 on a LAN 12 communicates with an end station 15 on another LAN 17 over this VC, and with an end station 20 on still another LAN 22 over the same VC. The VC in this case carries two flows: one from end station 10 to end station 15, and one from end station 10 to end station 20. The flows are handled by first and second routers 25, 27 and a series of ATM switches representatively indicated at 30, 32. Each router 25, 27 is connected to an illustrated LAN and to an ATM switch. The connection to an ATM switch is by means of an ATM interface configured to direct flows onto VCs; the routers establish further connections by means of additional interfaces, which may or may not be ATM interfaces. That is, each router 25, 27 may contain various interfaces for handling different types of network traffic.
Routers 25, 27 typically forward IP datagrams (i.e., operating at level 3 in the protocol stack by inspecting IP headers), terminating VCs at the ATM interfaces. ATM switches 30, 32 forward ATM cells (operating at level 2 in the protocol stack by examining ATM cell headers). VCs do not terminate on the interfaces of ATM switches 30, 32, instead passing through the switches. The VCs, then, span routers 25, 27, originating on one router and terminating on the other.
There may be more than one VC between router 25 and router 27. Furthermore, there may be additional VCs originating (or terminating) on routers 25 ,27 and terminating (or originating) on other routers not shown here.
The foregoing discussion assumes a continuous sequence of ATM switches intervening between ATM-capable routers 25, 27. Other device sequences are of course possible. For example, depending on the routing algorithm and communications costs, router 25 may direct traffic directly to router 27 and vice versa. Alternatively, one or more routers may intervene between ATM switches 30, 32. In this case, communication between end stations 10, 15 and 10, 20 would occur over paths defined by multiple sequential VCs, each terminating at a router.
Permitting communication resources to be shared among many communicating entities may lead to congestion. Routers and links have finite information-handling capacity (bandwidth), and if streams of packets arrive on several input lines all requesting the same output line, a queue will build up. Eventually, if the queue exceeds the buffering capacity of the router, packets will be lost.
One approach to congestion control is xe2x80x9ctraffic shaping,xe2x80x9d which regulates the average rate and concentration of data transferxe2x80x94that is, the traffic pattern. Limitations on transmission patterns are imposed on each VC with the goal of avoiding excessive data backup. These limitations are enforced by a xe2x80x9cshaper,xe2x80x9d usually implemented in hardware running on a router""s ATM network interfaces. The pattern adopted by a shaper may differ for different VCs and may also vary over time for a particular VC. If packets arrive at the router above the allowed VC transmission rate, then the network interface xe2x80x9cshapesxe2x80x9d the traffic sent on the VC to conform to that rate. As a result, packets must be buffered in the router circuitry or on the network interface itself. When this condition occurs, the VC is said to be xe2x80x9cbacklogged.xe2x80x9d
Another approach to traffic management is reactive rather than proactive. The bandwidth of the VC cannot be expanded, but at least it can be allocated among flows on the VC. xe2x80x9cFair queueingxe2x80x9d is a simple approach to bandwidth allocation in which a queue is defined for each flow seeking access to a given router output line. The router is programmed to scan the queues round robin, sequentially taking the first packet from each queue and transmitting it over the line. A flow, in this circumstance, is a series of packets requiring similar queueing treatment.
One problem with this approach is that it allocates more bandwidth to hosts that transmit large packets. Accordingly, fair queueing is typically implemented on a byte-by-byte, rather than on a packet-by-packet basis. A second problem is that all flows receive the same amount of bandwidth. In many situations, certain flows-such as those carrying critically important data-deserve greater bandwidth than others. A modified approach to fair queueing, called xe2x80x9cweighted fair queueingxe2x80x9d (WFQ), discriminates among flows by causing the network interface to transmit more bytes from certain queues during each pass, or to return to those queues more often than others.
Shaping and queueing represent different and in some ways complementary approaches to traffic management. Shaping limits traffic in an effort to avoid congestion, but does not attempt to ensure fairness in bandwidth allocation. WFQ criteria, by contrast, operate based on the specified characteristics of the flows rather than congestion on the VCs they use. For example, a packet due for transmission based on WFQ criteria may belong to a backlogged VC, and so cannot or should not be sent.
The present invention combines traffic shaping with per-flow fairness in intermediate stations operating on networks that support virtual circuits. In the case of a backlogged VC, the invention ensures that flows from the backlogged VC are temporarily suppressed notwithstanding their queue position. This suppression, however, is implemented in a manner that respects the queueing criteria. In other words, although traffic to backlogged VCs is limited in order to allow those lines to clear, this limitation occurs in a manner consistent with weighting or other per-flow fairness criteria. At the same time, packets destined for VCs which are not backlogged may still be sent.
In a first aspect, the invention comprises a router that receives packet flows from the network and transmits these packets onto another portion of the network. The router is equipped with two modules, which may be implemented as sequences of executable instructions or as hardware devices. The first module manages packet traffic by (i) defining output parameters, such as a traffic-shaping profile, that govern transmission of packets (or, more typically, flows of packets) over the network; and (ii) monitoring the transmission of packets over each output port for conformance to the transmission parameters. The traffic-management module may be a shaper, in which case the parameters define a traffic pattern that governs flow transmission. In an ATM environment, packet flows are associated with VCs, and the traffic pattern imposed by the shaper on a particular flow depends on the characteristics of the VC over which it travels. It should be emphasized that, in this environment, the shaping parameters vary with the VC and not with the physical port over which traffic for a particular VC is routed. At the same time, the invention can also be applied to routing devices having multiple output ports, with prioritization being used to allocate transmission resources among the physical ports themselves rather than among VCs.
The second module implements prioritization among packets by a queueing scheme, preferably (but not necessarily) WFQ, by (i) queueing received packets for transmission, and (ii) selecting packets for transmission based on a selection criterion. The prioritization module is responsive to the traffic-management module, postponing transmission of selected packets whose transmission would violate the transmission parameters (e.g., shaping requirements). In a WFQ implementation, the postponement duration is proportional to the weight associated with a particular packet (or flow).
The interaction between the first and second modules may be orchestrated such that the prioritization module, upon selecting a packet for transmission, interrogates the traffic-management module for indication of a shaping violation. The traffic-management module provides that indication if transmission of the selected packet would violate the transmission parameters associated with the packet. This mode of interaction facilitates scalability in the presence of many VCs; it is not necessary, for example, for a queueing component to assume a xe2x80x9cper-VCxe2x80x9d state (which would require a separate instance of the queueing component for each VC), since the queueing component can interrogate the traffic-management module (which naturally maintains separate per-VC states).
In a second aspect, the invention implements hysteresis by, for example, causing the traffic-management module to continue reporting a violation condition for a certain time period after the management criteria would permit transmission of the packet. It may then be able to accept more than one packet when it ceases reporting the violation condition. This can improve the overall fairness of prioritization by admitting packets from several flows. In this case the traffic-management module should be able to buffer a number of packets awaiting transmission.
In a third aspect, the invention is implemented on a network interface. An interface directs the input and output transactions of a router, typically receiving packet flows from a circuit and transferring these to the router""s input line, and transmitting, to a circuit, packet flows from the router output line. In accordance with the invention, the interface contains and implements the traffic-shaping and prioritization modules discussed above in connection with the output line for which it is responsible.
In a fourth aspect, the invention comprises methods implementing the foregoing operations.